package cluster;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Collections;
import common.Word;
import common.Config;

class Cluster implements Comparable<Cluster>{
    private LinkedList<Word> points = new LinkedList<Word>();
    public LinkedList<ClusterLink> links = new LinkedList<ClusterLink>(); 

    /**
     * keep points in cluster in decreasing order by weight
     */
    public void addPoint( Word w ){
        for( ListIterator<Word> it=points.listIterator();it.hasNext(); ){
            Word curw = it.next();
            if( curw.getWeight() < w.getWeight() ){
          	  it.previous();
                it.add( w );
                it.next();
                return;
            }
        }
        // w.weight is the smallest one
        points.add( w );
    }
    /**
     * keep links to be decreasing order by googness
     */
    public void addLink( ClusterLink clink ){
        for( ListIterator<ClusterLink> it=links.listIterator();it.hasNext(); ){
            ClusterLink curLink = it.next();
            if( curLink.goodness < clink.goodness ){
                it.previous();
                it.add( clink );
                it.next();
                return;
            }
        }
        // clink.goodness is the smallest one
        links.add( clink );
    }
    /**
     * get how many points this cluster containing
     */
    public int numPoints(){
	    return points.size();
    	}
    /**
     * find whether this Cluster contain a specific keyword,if true,update
     * it's weight.
     */
    public boolean containWord( Word word ){
        for( ListIterator<Word> it=points.listIterator();it.hasNext(); ){
            Word myword = it.next();
            if( myword.getKeyword().equals( word.getKeyword() ) ){
                // if needed,update weight
                if( word.getWeight()!=0 )
                    myword.setWeight( word.getWeight() );
                return true;   
            }
        }
        return false;
    }

    /**
     * 找出和本簇goodness最大的簇
     */
    public Cluster closest(){
        ClusterLink clink = links.peekFirst();
        return clink== null?null:clink.cl;
    }

    /**
     * 找出邻居列表中最大的goodness
     */
    public float maxGoodness(){
        ClusterLink clink = links.peekFirst();
        return clink==null?0:clink.goodness;
    }

    public int compareTo( Cluster another ){
        return Float.compare( this.maxGoodness(),another.maxGoodness() );
    }

	/**
	 * 将another簇中的关键词合并到本簇中,有序列表的合并操作(两个簇内不可能含有同一个关键词)
	 */
    private void mergePoints( LinkedList<Word> another ){
        ListIterator<Word> it = points.listIterator();
        ListIterator<Word> iter = another.listIterator();
        
        while( iter.hasNext() ){
            Word hisword = iter.next();
            boolean added = false;
                    
            while( it.hasNext() ){
                Word myword = it.next();
                assert( myword!=hisword );
                if( hisword.getWeight() > myword.getWeight() ){
          	      // add hisword before myword
          	      it.previous();
          	      it.add( hisword );
                	
                	added = true;
                	break;
                			}
            		}
            	// another中剩余关键词权重小于points中的最小的
            if( added==false ){
          	  it.add( hisword );
			}
        		}
        // 
    }

    private float fun( int n ){
        float t= Config.thta;
        float e = (1-t)/(1+t);
        return (float)Math.pow( n,1+2*e );
    }	

	/**
	 * 重新计算link.cl与簇clink的goodness
	 */
	private void recomputeGoodWith( ClusterLink clink ){
		int n1 = this.points.size();
		int n2 = clink.cl.points.size();
		int linkNum = clink.num;
        clink.goodness = (float)linkNum/(fun(n1+n2)-fun(n1)-fun(n2));		
	}

	/**
	 * 计算本簇与邻居列表中各簇的goodness
	 */
	private void computeLinksGood(){
		for( ListIterator<ClusterLink> it = links.listIterator();it.hasNext(); ){
			ClusterLink clink = it.next();
			recomputeGoodWith( clink );
		}
	}

    /**
     * 重新计算列表各元素的goodness，对邻居列表中各簇按goodness减序排列
     */
	public void sortLinks(){
		computeLinksGood();
		// todo sort by goodness
        Collections.sort( links );
        Collections.reverse( links );
	}

	/**
	 * 将簇another中的邻居列表合并到本簇，列表中相同的元素则累加link,
     *并重新计算列表各元素的goodness,再排序
	 */
    private void mergeLinks( LinkedList<ClusterLink> another ){
        ListIterator<ClusterLink> iter = another.listIterator();
		while( iter.hasNext() ){
			ClusterLink hislink = iter.next();
			boolean added = false;
			
			// Connot be itself link
			if( hislink.cl == this ){
				continue;
			}
			ListIterator<ClusterLink> it = links.listIterator();
			//find the link whether exsits
			while( it.hasNext() ){
				ClusterLink mylink = it.next();
				if( mylink.cl == hislink.cl ){
					mylink.num += hislink.num;
					added = true;
					break;
				}
			}
			//not found,add it
			if( added==false ){
				// add hisword before myword
				it.add( hislink );
			}
        }
		sortLinks();
    }

	public void merge( Cluster another ){
		mergePoints( another.points );
		mergeLinks( another.links );
	}

    /**
     * 两个簇合并后，更新邻居列表中包含这两个簇中至少一个的邻居列表,(algor
     * ghtm to be improved)
     */
    public void updateLinkList( Cluster mergeTo,Cluster merged ){
        ClusterLink tolink = null;
        ClusterLink edlink = null;
        
        // 在邻居列表中查找簇mergeTo和merged,先从邻居列表中分离开
        for( ListIterator<ClusterLink> it=links.listIterator();it.hasNext(); ){
            ClusterLink clink = it.next();
            if( clink.cl == mergeTo ){
          	  tolink = clink;
                // 两个簇都存在，无需进一步搜索
          	  it.remove();
               if( edlink!=null ){
                    break;
                			}
            }
            else if( clink.cl == merged ){
                edlink = clink;
                it.remove();
                if( tolink!=null ){
          	      break;
                			}
            }
        }
        // 只需考虑以下3种情况即可
        if( tolink!=null && edlink!=null ){
            // 两个簇都存在
            tolink.num += edlink.num;
            recomputeGoodWith( tolink );
            // 重新添加合并后的簇
            addLink( tolink );
        }
        else if( tolink!=null && edlink==null ){
	    // mergeTo exsits,but merged doesn't
	        addLink( tolink );
        		}
        else if( tolink==null && edlink!=null ){
            // mergeTo不存在,merged存在
            edlink.cl = mergeTo;
            recomputeGoodWith( edlink );
            addLink( edlink );
        }
    }
    /**
     * if Cluster toRemove is link to this cluster,remove it.Otherwise,do nothing.
     * @param toRemove
     */
	public void ifRemoveLink( Cluster toRemove ){
		for( ListIterator<ClusterLink> it=links.listIterator();it.hasNext(); ){
			if( it.next().cl == toRemove ){
				it.remove();
				return;
			}
		}
	}
	public String toString(){
		//debug
		//System.out.println( "points.size() is:"+points.size() );
		//end
		return points.toString();
	}
}
